1. Field of the Invention
The invention relates to the field of circuit design and, more particularly, to the use of implementation sets in a tree representation for implementing a circuit design.
2. Description of the Related Art
Circuit designs, and particularly designs for Field Programmable Gate Arrays (FPGA's), have become increasingly complex and heterogeneous. The rapid increase of FPGA design complexity and size has driven several complex Xilinx FPGA devices to accommodate a few million gates. Modern circuit designs can include a variety of different components or resources including, but not limited to, registers, block Random Access Memory (RAM), multipliers, processors, and the like. This increasing complexity makes design tools, maintenance of design tools as well as placement and signal routing of circuit designs more cumbersome. Existing design tools can have multiple flows that fail to be uniform, further adding to the complexity in the tools and their maintenance. Furthermore, existing design tools fail to provide sufficient flexibility in terms of representing design granularity in a particular design.
With such an enormous increase in device capacity and complexity, the traditional flattened design implementation methodology is faced with challenges in obtaining a good design implementation in an acceptable time frame. Since the design is flattened and implemented all at once in the traditional flattened design implementation methodology, a design of large size can easily cause a sophisticated algorithm employed in a tool flow to fail in the run-time without guaranteeing a good solution. Consequently, a divide-and-conquer methodology is usually considered for difficult and perhaps sometimes impossible large design implementations. In a divide-and-conquer methodology, the design is first divided into several sub-designs. Since each sub-design is only a small portion of the original design, a good implementation can be obtained in a fairly reasonable amount of time. Then, a complete implementation of the entire design can be formed by assembling the implementations for the sub-designs.
Xilinx software implementation tools currently support a number of user flows including a “conventional flow” and a set of “user interactive” flows. The conventional flow is characterized by a single design iteration while the user interactive flows require two (2) or more design iterations through the tools. These user interactive flows refer to a collection of 5 flows, namely Normal Guide Exact flow, Normal Guide Leverage flow, Incremental Design flow, Modular Design flow, and Partial Reconfiguration flow. Each flow addresses a specific set of customer needs.
For Normal Guide Exact flow, its primary use is to incorporate design changes based upon a previous physical implementation where the underlying objective is to incorporate the changes while preserving the performance of the previous implementation. As for Normal Guide Leverage and Incremental Design flows, their primary applications are also to incorporate and implement design changes to an existing design. However, the objective for Normal Guide Leverage and Incremental Design flow is to minimize the overall implementation run-time.
For Modular Design flow (and its derived variations such as Partial Reconfiguration flow), it serves two primary use cases, namely: (1) to provide a software infrastructure that allows for a divide-and-conquer approach used to manage design complexity by tackling smaller sub-designs; and (2) to provide a software infrastructure to support a parallel team design environment where a single design is divided into sub-designs. In turn, each partitioned sub-design is implemented independently by different team members. The final design is then assembled from previously implemented sub-designs. During the assembly phase, the user can choose to assemble the implemented sub-designs all at once or one sub-design at a time. When the implemented sub-designs are assembled sequentially, the user can specify a preferred ordering of sub-designs to follow during the assembly process. This sequential assembly process allows the user to be able to examine the quality of each intermediate partially assembled implementation. If a partially assembled implementation fails to meet all the design goals, re-implementing sub-design(s) can start early, instead of at the end of the assembly.
Lastly, the Partial Reconfiguration flow takes advantage of the underlying Xilinx FPGA device feature of partial bit stream re-programming which allows for the loading of a partial bit stream onto a Xilinx FPGA device while it is active and operational on the unchanged bit stream portion. From a software perspective, the Partial Reconfiguration flow is supported as a sub-flow or a variation of the Modular Design flow.
Due to historical reasons, each of the user interactive flows has been designed separately and for the most part defect driven. The evolution of these flows has taken separate and independent paths. Without a common theme among these user interactive flows, it was inevitable that the relevant concepts, methodology, and implementation became fractured. As a result, inefficiencies arose and customer flow complexity increased. Each interactive flow required a different set of knowledge, terminology, and procedure that posed as an obstacle to ease-of-use. In addition, the internal implementation increased in the development overhead as each user interactive flow was supported separately.
One of the root causes identified for why the prior interactive flows diverged was that each interactive flow operated on a different notion or implementation of how a partial net-list is specified. Specifically, under Incremental Design flow, the partial net-list of interest is specified by the contents of an Area Group. Similarly, under Modular Design and Partial Reconfiguration flows, the partial net-list is specified by either an Active Module or a previously implemented module (or PIM). Lastly, under Normal Guide Exact, Leverage, and conventional flows, the partial net-list is given by the entire design. As the result, the client application implementations became dependent of each flow and required the software overhead of understanding and processing the various data representations. In addition, due to the complexity of each interactive flow, the software maintenance and enhancements became an increasing overhead and burden on engineering staff resources. Furthermore, there were other notions of partial net-lists in the software system such as: modules, hard macro, and soft Intellectual Property (IP) core. Each of these design entities were implemented and supported separately. As the software system evolves with an increasing number of these design entities, the resulting software complexity and impact will be significant.
Many of the tasks performed in these interactive flows relate to working with containers of grouped logic. Flows are determined in part by user specified command line parameters and user-specified constraints. Point tools read the parameters from the command line and the constraint file, and operate on the groups of logic with algorithms that are dependent on the particular flow that is being followed. The algorithms are fractured and branch into other algorithms depending on characteristics such as the flow information and the additional parameters that defines the grouped logic. As noted above, changes to the flow definition may require extensive modification to underlying algorithms.
In existing systems, individual point tools would use flow information to change the behavior of algorithms. For example, a tool may need to know if it should guide all of a container of logic, or none of it. The tool would determine the flow, and perhaps not guide the container if it had a change to the logic and it was in the Incremental Design flow. In other words, flow information was interspersed widely throughout the point tools' algorithms. For instance, in the Modular Design flow, Place and Route tools read data from the command line, but the existence of Active Modules in the design database would invoke a different algorithm than was originally being processed. The distributed nature of flow information throughout the algorithms has many disadvantages. A specified flow is a very high level concept that affects many low-level decisions. Any changes to the high-level flow information will result in changes to the code in many different places that can result in costly coding errors. Relatively minor changes to the flow can result in major modifications to the underlying algorithms. Consequently, it is difficult to support new flows or modify existing flows.